package test;


import java.util.*;

public class exercise1 {
    //冒泡排序
    public void bubbleSort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = 0; j < arr.length - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = arr[j];
                }
            }
        }
    }
    public boolean chkRotation(String A,String B) {
        if(A.length()!=B.length()){
            return false;
        }
        String AA = A + A;
        return AA.contains(B);
    }
    //选择排序
    public void selectSort(int[] arr) {
        int minIndex, temp;
        for (int i = 0; i < arr.length - 1; i++) {
            minIndex = i;
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            temp = arr[minIndex];
            arr[minIndex] = arr[i];
            arr[i] = temp;
        }
    }

    //插入排序
    public void insertSort(int[] arr) {
        int current, preIndex;
        for (int i = 1; i < arr.length; i++) {
            current = arr[i];//保存当前值
            preIndex = i - 1;
            while (preIndex > 0 && current < arr[preIndex]) {
                arr[preIndex + 1] = arr[preIndex];//将小的值往前移
                preIndex--;
            }
            arr[preIndex + 1] = current;//preIndex多减1
        }
    }

    //希尔排序
    public void shellSort(int[] arr) {
        int current, preIndex;
        for (int step = arr.length / 2; step > 0; step = step / 2) {
            for (int i = step; i < arr.length; i = i + step) {
                current = arr[i];
                preIndex = i - step;
                while (preIndex > 0 && current < arr[preIndex]) {
                    arr[preIndex + step] = arr[preIndex];
                    preIndex = preIndex - step;
                }
                arr[preIndex + step] = current;
            }
        }
    }

    //快速排序
    public void quickSort(int[] arr, int left, int right) {
        if (left < right) {
            int start = arr[left];
            int low = left;
            int high = right;
            while (low < high) {
                while (low < high && arr[high] >= start) {//避免减过头
                    high--;
                }
                arr[low] = arr[high];
                while (low < high && arr[low] <= start) {
                    low++;
                }
                arr[high] = arr[low];
            }
            arr[low] = start;
            quickSort(arr, left, low);
            quickSort(arr, low + 1, right);
        }
    }

    //归并排序
    public void mergeSort(int[] arr, int left, int right, int[] temp) {
        int mid = left + (right - left) / 2;
        if (left < right) {
            mergeSort(arr, left, mid, temp);
            mergeSort(arr, mid + 1, right, temp);
            //合并
            merge(arr, left, mid, right, temp);
        }
    }

    private void merge(int[] arr, int left, int mid, int right, int[] temp) {
        int index = 0;
        int leftIndex = left;
        int rightIndex = mid + 1;
        while (leftIndex <= mid && rightIndex <= right) {
            if (arr[leftIndex] > arr[rightIndex]) {
                temp[index++] = arr[rightIndex++];
            } else {
                temp[index++] = arr[leftIndex++];
            }
        }
        while (leftIndex <= mid) {
            temp[index++] = arr[leftIndex++];
        }
        while (rightIndex <= right) {
            temp[index++] = arr[rightIndex++];
        }
        index = 0;
        int tempLeft = left;
        while (tempLeft <= right) {//left到right
            arr[tempLeft++] = arr[index++];
        }
    }

    //链表翻转 迭代
    public ListNode reverseNode(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        ListNode next;
        while (cur != null) {
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }

    //链表翻转 递归
    public ListNode reverseNode1(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        } else {
            ListNode reverseNode1 = reverseNode1(head.next);
            head.next.next = head.next;
            head.next = null;
            return reverseNode1;
        }
    }

    //链表翻转 翻转中间几个链表
    public ListNode reverseBetween(ListNode head, int left, int right) {
        ListNode newNode = new ListNode(-1);
        newNode.next = head;
        ListNode pre = newNode;
        ListNode cur;
        for (int i = 1; i < left; i++) {
            pre = pre.next;
        }
        cur = pre.next;
        ListNode next;
        for (int i = 0; i < right - left; i++) {
            next = cur.next;
            cur.next = next.next;
            next.next = pre.next;
            pre.next = next;
        }

        return newNode.next;

    }

    //链表倒数第K个值 非递归
    public ListNode lastK(ListNode head, int k) {
        if (k <= 0) return null;
        ListNode left = head;
        ListNode right = head;
        for (int i = 0; i < k - 1; i++) {
            if (right == null) return null;
            right = right.next;
        }
        if (right == null) return null;
        while (right.next != null) {
            left = left.next;
            right = right.next;
        }
        return left;
    }

    //链表倒数第K个值 递归
    public ListNode lastK1(ListNode head, int k, MyCount myCount) {
        if (head == null) {
            return null;
        } else {
            ListNode listNode = lastK1(head.next, k, myCount);
            myCount.value = myCount.value + 1;
            if (myCount.value == k) {
                return head;
            }
            return listNode;
        }
    }

    //删除链表中倒数第n个节点
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode newListNode = new ListNode(-1);
        newListNode.next = head;
        ListNode pre = newListNode;
        ListNode left = pre.next;
        ListNode right = pre.next;
        for (int i = 0; i < n - 1; i++) {
            if (right == null) return null;
            right = right.next;
        }
        if (right == null) return null;
        while (right.next != null) {
            left = left.next;
            right = right.next;
            pre = pre.next;
        }
        pre.next = pre.next.next;
        return newListNode.next;
    }

    //合并两个有序数组
    public void merge(int[] nums1, int[] nums2, int m, int n) {
        int k = m + n;
        int index1 = m - 1;
        int index2 = n - 1;
        for (int index = k - 1; index >= 0; index--) {
            if (index1 < 0) {
                nums1[index] = nums2[index2--];
            } else if (index2 < 0) {
                //nums1[index] = nums1[index1--];
                break;
            } else if (nums1[index1] < nums2[index2]) {
                nums1[index] = nums2[index2--];
            } else {
                nums1[index] = nums1[index1--];
            }
        }
    }

    //合并两个有序链表
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if (list1 == null) return list2;
        if (list2 == null) return list1;
        ListNode listNode = new ListNode(0);
        ListNode p = listNode;
        ListNode listNode1 = list1;
        ListNode listNode2 = list2;
        while (listNode1 != null && listNode2 != null) {
            if (listNode1.val < listNode2.val) {
                p.next = listNode1;
                listNode1 = listNode1.next;
            } else {
                p.next = listNode2;
                listNode2 = listNode2.next;
            }
            p = p.next;
        }
        if (listNode1 != null) {
            p.next = listNode1;
        }
        if (listNode2 != null) {
            p.next = listNode2;
        }
        return listNode.next;
    }

    //合并两个有序链表 递归实现
    public ListNode mergeTwoLists1(ListNode list1, ListNode list2) {
        if (list1 == null) return list2;
        if (list2 == null) return list2;
        if (list1.val < list2.val) {
            list1.next = mergeTwoLists1(list1.next, list2);
            return list1;
        }
        list2.next = mergeTwoLists1(list1, list2.next);
        return list2;
    }

    //删除链表重复元素
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode cur = head;
        while (cur != null && cur.next != null) {
            if (cur.next.val == cur.val) {
                cur.next = cur.next.next;
            } else {
                cur = cur.next;
            }
        }
        return head;
    }

    //删除链表重复元素 递归实现
    public ListNode deleteDuplicates1(ListNode head) {
        if (head == null || head.next == null) return head;
        head.next = deleteDuplicates(head.next);
        if (head.next.val == head.val) {
            return head.next;
        } else {
            return head;
        }
    }

    //环形链表II
    public ListNode detectCycle(ListNode head) {
        if (head == null) return null;
        ListNode slow = head;
        ListNode fast = head;
        boolean flag = false;
        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next.next;
            if (fast == slow) {
                flag = true;
                break;
            }
        }
        if (flag) {
            slow = head;
            while (slow != fast) {
                slow = slow.next;
                fast = fast.next;
            }
            return slow;
        } else {
            return null;
        }
    }

    //两个数组的交集 排序+双指针法
    public int[] intersection(int[] nums1, int[] nums2) {
        List<Integer> list = new ArrayList<>();
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        int index1 = 0;
        int index2 = 0;
        while (index1 < nums1.length && index2 < nums2.length) {
            if (nums1[index1] < nums2[index2]) {
                index1++;
            } else if (nums1[index1] > nums2[index2]) {
                index2++;
            } else {
                if (list.size() == 0 || list.get(list.size() - 1) != nums1[index1]) {
                    list.add(nums1[index1]);
                }
                index1++;
                index2++;
            }
        }
        int[] nums = new int[list.size()];
        for (int i = 0; i < nums.length; i++) {
            nums[i] = list.get(i);
        }
        return nums;
    }

    //两个数组的交集 hashSet
    public int[] intersection1(int[] nums1, int[] nums2) {
        HashSet<Integer> integers = new HashSet<>();
        HashSet<Integer> result = new HashSet<>();
        for (int k : nums1) {
            integers.add(k);
        }
        for (int j : nums2) {
            if (integers.contains(j)) {
                result.add(j);
            }
        }
        int[] ints = new int[result.size()];
        int index = 0;
        for (int i : result) {
            ints[index++] = i;
        }
        return ints;
    }

    //相交链表
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) return null;
        ListNode a = headA;
        ListNode b = headB;
        while (a != b) {
            a = a == null ? headB : a.next;
            b = b == null ? headA : b.next;
        }
        return a;
    }

    //回文链表
    public boolean isPalindrome(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        if (fast != null) {
            slow = slow.next;
        }
        ListNode pre = null;
        ListNode cur = slow;
        ListNode next;
        while (cur != null) {
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        slow = pre;
        fast = head;
        while (slow != null) {
            if (slow.val != fast.val) {
                return false;
            }
            slow = slow.next;
            fast = fast.next;
        }
        return true;
    }

    //对称二叉树 递归实现
    public boolean isSymmetric(TreeNode root) {
        if (root == null) return true;
        return deepcheack(root.left, root.right);
    }

    public boolean deepcheack(TreeNode left, TreeNode right) {
        if (left == null && right == null) return true;
        if (left == null || right == null) return false;
        if (left.val != right.val) {
            return false;
        }
        return deepcheack(left.left, right.right) && deepcheack(left.right, right.left);
    }

    //对称二叉树 队列迭代实现
    public boolean isSymmetric1(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        if (root == null) return true;
        if (root.left == null && root.right == null) return true;
        if (root.left == null || root.right == null) return false;
        queue.offer(root.left);
        queue.offer(root.right);
        while (!queue.isEmpty()) {
            TreeNode l = queue.poll();
            TreeNode r = queue.poll();
            if (l == null && r == null) continue;
            if (l == null || r == null) return false;
            if (l.val != r.val) return false;
            queue.offer(l.left);
            queue.offer(r.right);
            queue.offer(l.right);
            queue.offer(r.left);
        }
        return true;
    }

    //二叉树最大深度 递归
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;
        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }

    //二叉树最大深度 队列实现
    public int maxDepth1(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        if (root == null) return 0;
        queue.offer(root);
        int depth = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            while (queue.size() > 0) {
                TreeNode node = queue.poll();
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
                size--;
            }
            depth++;
        }
        return depth;
    }

    //平衡二叉树
    public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        }
        return helper(root) != -1;
    }

    public int helper(TreeNode root) {
        if (root == null) return 0;
        int left = helper(root.left);
        int right = helper(root.right);
        if (left == -1 || right == -1 || Math.abs(left - right) > 1) {
            return -1;
        }
        return Math.max(left, right) + 1;
    }

    //有效的括号
    public boolean isValid(String s) {
        Deque<Character> deque = new LinkedList<>();
        for (char c:s.toCharArray()){
            if (c == '('){
                deque.push(')');
            }else if (c == '{'){
                deque.push('}');
            }else if(c == '['){
                deque.push(']');
            }else {
                if (deque.isEmpty() || deque.pop() != c){
                    return false;
                }
            }
        }
        return deque.isEmpty();
    }


}

class MyCount {
    public int value = 0;
}

class ListNode {
    int val;
    ListNode next;

    public ListNode() {

    }

    public ListNode(int val) {
        this.val = val;
    }

    public ListNode(int val, ListNode next) {
        this.next = next;
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}